#! /usr/bin/python

from random import uniform, randint
from itertools import combinations


def random_sample(*args):
    seq = args[0]
    try:
        rest = float(len(seq))
        nsamples = args[1]
    except:
        rest = float(args[1])
        nsamples = args[2]

    result = []
    for item in seq:
        threshold, probability = nsamples / rest, uniform(0, 1)
        if probability < threshold:
            result.append(item)
            nsamples -= 1
        rest -= 1
        if nsamples == 0:
            break

    return result


def generate_weighted_edges(num_vertices, num_edges):
    '''Generates edges for a weighted graph.
       Args:
         num_vertices
         num_edges

      Returns:
         dictionary with the edges; in the dictionary keys
         are edges whereas the values are corresponding weights.

         optimal path in the graph. distance between every pair of nodes
         equals to 1.
    '''
    min_weight = num_vertices + 1
    vertices = range(num_vertices)
    edges = {}

    pairs, pairs_count = combinations(vertices, 2), \
        num_vertices * (num_vertices - 1)
    for u, v in random_sample(pairs, pairs_count, num_edges):
        edges[u, v] = randint(min_weight, 10 * min_weight)

    path = random_sample(vertices, num_vertices / 2)
    u = path[0]
    for v in path[1:]:
        edges[u, v] = 1
        u = v

    return edges, path


if __name__ == '__main__':

    def test_random_sample():
        from collections import defaultdict

        ntests = 2000000
        nsamples = 10
        nitems = 200

        seq, freqs = range(nitems), defaultdict(int)
        for i in range(ntests):
            samples = random_sample(seq, nsamples)
            for item in samples:
                freqs[item] += 1

        minfr, maxfr = 1.0, 0.0
        for key, value in freqs.items():
            frequency = float(value) / ntests
            if frequency < minfr:
                minfr = frequency
            elif frequency > maxfr:
                maxfr = frequency

        return minfr, maxfr

    print test_random_sample()
